1. Field of the Invention
The invention relates to an apparatus for arbitrating access priority of a volatile memory for a plurality of circuit modules and a method related thereto, and more particularly, to an apparatus for classifying circuit modules into different groups to arbitrate access priority parallelly, and related method, so as to shorten the arbitrating time and to simplify the circuit arrangement of the apparatus.
2. Description of the Prior Art
Controllers are an important building block of modern information systems. Controllers are capable of complex calculations and management of data, and so are used in various automatic devices and computer systems. As technology becomes more sophisticated, the number of circuits integrated into a controller increases, and this provides the controller with an increasingly more powerful and complex functionality.
A controller contains a plurality of circuit modules with different functions. Aggregating the different functions of these circuit modules provides the entire functionality of the controller. A controller may integrate a volatile memory that is a shared resource for all of the circuit modules. For example, a controller integrates a memory, preferably a static random access memory (SRAM) for storing operational data for each circuit module, and each of the circuit modules accesses the memory to complete its respective function. To effectively manage the system resources in the controller, only a predetermined number of circuit modules can access the same volatile memory in a period of time, and the controller thus contains arbiters to control each circuit module to manage the same volatile memory resource. Please refer to FIG. 1, which is a schematic diagram of function blocks of a typical controller 10. The controller 10 may be, for example, a switch controller used in a network switch, managing the exchange of information between network terminals. As shown in FIG. 1, application circuits CP1–CP56 are block circuits in the controller 10, which respectively perform every essential function of the controller 10. In the controller 10, the application circuits CP1–CP56 commonly access volatile memory 12 of the controller 10. For managing access to the volatile memory 12 of CP1–CP56, an arbiter 14 is usually provided in the controller 10. When an application circuit CP1–CP56 seeks to access the volatile memory 12, the application circuit CP1–CP56 sends a request signal to the arbiter 14. Since the volatile memory 12 can only serve a predetermined number of application circuits CP1–CP56, the arbiter 14 will select only the predetermined number of application circuits CP1–CP56 to access the volatile memory 12 when more than the predetermined amount of application circuits CP1–CP56 send request signals at the same time. The other unselected application circuits CP1–CP56 are not granted access to the volatile memory 12 at this stage. In practice, the arbiter 14 and every application circuit of the controller 10 are driven by a clock signal CLK, which has a period T. The arbiter 14 accepts request signals from each application circuit in a clock cycle (i.e., the time period T0 as shown in FIG. 1), and then allows a proper amount of application circuits CP1–CP56 to access the volatile memory 12, as per their individual requests, in the next clock cycle (the time period T1). In other words, the arbiter 14 must decide, in the current clock cycle (time period T0), which application circuits CP1–CP56, among all of the application circuits CP1–CP56 that send request signals, can actually access the volatile memory 12 in the next clock cycle (time period T1).
To decide which application circuits CP1–CP56 can actually access the volatile memory 12, every circuit application CP1–CP56 has an access priority individually. The arbiter 14 first selects those application circuits CP1–CP56 with the highest priority among all application circuits CP1–CP56 that send request signals, and these highest-priority application circuit CP1–CP56 are then permitted to access the memory 12. By way of example, assume that the controller 10 contains application circuits CP1–CP56 that share the volatile memory 12, and the volatile memory 12 can only serve four application circuits in a same time period (i.e., in a same clock cycle). The application circuit with the highest priority is application circuit CP1, the application circuit with the second highest priority is application circuit CP2, and so on; the application circuit with the lowest priority is thus application circuit CP56. In other words, the priority of application circuit CP1 is higher than the priority of application circuit CP2; the priority of application circuit CP2 is higher than the priority of application circuit CP3; and so on. If application circuits CP2, CP3, CP27, CP29, CP58, CP57, and CP56 all send request signals in the time period T0, the arbiter 14 will select the four application circuits with the highest priority: application circuits CP2, CP3, CP27, and CP29 are thus selected, as the volatile memory 12 can only simultaneously serve four application circuits. The four selected application circuits CP2, CP3, CP27, and CP29 can then access the volatile memory 12.
Please refer to FIG. 2, which is a function block diagram according to prior art of the arbiter 14 shown in FIG. 1. Continuing with the previous example, the controller 10 contains 56 application circuits, and the arbiter 14 must select the four application circuits with the highest priority among a plurality of the application circuits sending request signals. Therefore, arbiter modules 21–24, which select 1 output from 56 inputs (56-to-1), are provided in the arbiter 14 to select an application circuit with a highest respectively priority. The application circuits are all connected to the arbiter 14. When an application circuit sends a request signal, it sends a high level signal on its corresponding request trace; when the application circuit is not sending a request signal, it keeps the voltage of its corresponding trace low. In FIG. 2, traces RP1–RP56 are the traces of application circuits CP1–CP56 for transferring request signals to arbiter 14. The 56 traces can be treated as an input bus REQ0 of the arbiter 14, and the input REQ0 is provided to every arbiter module 21–24. After the arbiter module 21 receives the input REQ0, it selects an application circuit with the highest priority among the application circuits sending request signals, and generates a corresponding output GR1. In practice, the arbiter module 21 can use another 56 traces to form the output GR1, wherein each trace of the 56 traces corresponds to an application circuit respectively. The arbiter module 21 outputs a high level signal on the trace corresponding to the selected application circuit, and keeps the other traces low. The arbiter module 22 then selects an application circuit with the second highest priority among the application circuits sending request signals. Thus the arbiter module 22 not only needs to know which application circuits have sent request signals, but also needs to know which application circuit was selected by the arbiter module 21, as obtained from the output GR1 of the arbiter module 21. The arbiter module 22 also sends an output GR2, which is a combination of 56 traces. Similarly, the arbiter module 23 selects an application circuit with the third highest priority after the arbiters 21 and 22 have selected one application circuit respectively. The arbiter module 23 needs to receive the input REQ0, the output GR1 of the arbiter module 21, and the output GR2 of the arbiter module 22, and thereby selects an application circuit with the third highest priority to produce a corresponding output GR3. Finally, the arbiter module 24 receives input REQ0 and outputs GR1, GR2, and GR3 of arbiters 21–23 to select an application circuit with the fourth highest priority, generating a corresponding output GR4. Collecting the four application circuits selected by arbiter modules 21–24, the arbiter 14 produces an output bus GRN0, wherein the output GRN0 is formed from 56 traces respectively corresponding to each application circuit. According to the four selected application circuits, the arbiter 14 raises the voltages of the four traces to high, indicating that the arbiter 14 permits the four selected application circuits to access the volatile memory 12. The voltages of the other traces of the unselected application circuits, because of their lower priority, and the application circuits not sending request signals, are kept low, indicating that those application circuits are not permitted to access the volatile memory 12. In FIG. 2, the traces GP1–GP56, which form the output GRN0, correspond to application circuits CP1–CP56 respectively.
A practical example is used in the following to illustrate the operation of arbiter 14. If seven application circuits CP2, CP3, CP27, CP29, CP53, CP54, and CP56 assert request signals in a time period T0 (with reference to FIG. 1), the traces RP2, RP3, RP27, RP29, RP53, RP54, and RP56 of the input REQ0 will be high (indicated by mark “H” in FIG. 2). The arbiter module 21 selects the application circuit CP2, which has the highest priority, from the seven application circuits mentioned above, then raises the trace, which corresponds to application circuit CP2, of the output GR1 to high (CP2 is thus indicated in parentheses). The arbiter module 22 then selects application circuit CP3, which has the second highest priority, from the seven application circuits according to the input REQ0 and output GR1. The arbiter module 22 also raises the corresponding trace of application circuit CP3 to high in its output GR2. In practice, the structures of the arbiter modules 22–24 are nearly identical to the structure of the arbiter module 21. The arbiter module 22 uses the output GR1 of the arbiter module 21 to mask the application circuit CP2 selected by arbiter module 21, so the arbiter module 22 will select the application circuit CP3 with the highest priority among the six application circuits CP3, CP27, CP29, CP53, CP54, and CP56. Then, the arbiter module 23 uses the outputs GR1 and GR2 to mask to request signals of application circuits CP2 and CP3, and therefore arbiter module 23 chooses the application circuit CP27 from application circuits CP27, CP29, CP53, CP54, and CP56 and sets the trace corresponding to the output GR3 high. Finally, the arbiter module 24 selects the application circuits CP29 after application circuits CP2, CP3, and CP27 are masked. Collecting the selected application circuits CP2, CP3, CP27, and CP29, the four traces GP2, GP3, GP27, and GP29 in the output GRN0 of the arbiter 14 are raised high. In the time period T1 after T0 (in FIG. 1), the controller 10 permits the application circuits CP2, CP3, CP27, and CP29 to access the volatile memory 12 according to the output GRN0 of the arbiter 14. In another aspect, if only two application circuits CP2 and CP54 send request signals in time period T0, arbiter modules 21 and 22 will select the application circuits 21 and 22 respectively, and the other arbiter modules 22 and 23 will not raise the outputs GR3 and GR4. In other words, the arbiter modules 23 and 24 will not give access permission to any other application circuits.
The disadvantages of the arbiter 14 of the prior art are discussed in the following. First, every arbiter module 21–24 has to handle the input REQ0 from every application circuit of the controller 10, so each arbiter module is formed from many logic gates. In the above example, there are 56 application circuits in the controller 10 that may request access to the volatile memory 12 at the same time, and so the arbiter modules 21–24 all need to have the ability to select as output 1 input from 56 inputs (56-to-1 functionality). The inputs and outputs of arbiter modules 21–24 all have 56 traces, and this means that up to 56*56 inputs and outputs must be provided. Achieving such functionality requires a large number of logic gates to form the arbiter modules 21–24. When the gate count of the prior-art arbiter 14 increases, the associated cost of die area and energy consumption correspondingly increase. Furthermore, the associated propagation delay of each arbiter module 21–24 will also increase when the gate count increases. As discussed above, the arbiter modules 21–24 have to work in a sequential order to select the four application circuits having the highest priorities. The arbiter module 22 depends upon the output GR1 of the arbiter module 21 to select the application circuit having the second highest priority; the arbiter module 23 depends on the outputs GR1 and GR2 of the arbiter modules 21 and 22 to select the application circuit having the third highest priority; and the arbiter module 24 can not select the application circuit having the fourth highest priority until the operations of arbiter modules 21–23 are finished. The arbiter 14 thus must function in the sequential order of arbiter modules 21, 22, 23, and 24 to finish the arbitration, and the total propagation time is thus the sum of the propagation delays of each arbiter module 21–24. Based upon demands placed upon the controller 10, the arbiter 14 may have to finish arbitration in a single clock cycle. Hence, if the total propagation delay is so long that the arbiter 14 cannot finish the arbitration in a clock cycle, the controller 10 will either not work properly, or the controller 10 will require a longer clock cycle. As a result, the prior-art arbiter 14 requires long clock cycles, but the internal frequency of a modern controller goes high.